package erchashu;

import java.util.Stack;

/**
 * @program: jvm
 * @description
 * @author: tkk fendoukaoziji
 * @create: 2019-05-04 22:48
 **/
public class Tree {
    private Node root;
    public Tree(){
        root=null;
    }
    public Node find(int key){//find node with given key
        Node current=root;
        while(current.iData!=key){
            if(key<current.iData){
                current=current.leftChild;
            }else {
                current=current.rightChild;
            }
            if(current==null){
                return null;
            }
        }//end while
        return current;
    }//end find
    public void insert(int id,double dd){
        Node newNode=new Node();
        newNode.iData=id;
        newNode.dData=dd;
        if(root==null){
            root=newNode;
        }else{
            Node current=root;
            Node parent;
            while (true){
                parent=current;
                if(id<current.iData){
                    current=current.leftChild;
                    if(current==null){
                        parent.leftChild=newNode;
                        return ;
                    }
                } else{
                        current=current.rightChild;
                        if(current==null){
                            parent.rightChild=newNode;
                            return;
                        }
                }//end else right
            }//end while
        }//end  not root
    }
    public boolean delete(int key){
        Node current =root;
        Node parent=root;
        boolean isLeftChild=true;
        while(current.iData!=key) {
            parent = current;
            if (key < current.iData) {//go to leftChild
                current = current.leftChild;
                isLeftChild = true;
            } else { // or go right
                isLeftChild = false;
                current = current.rightChild;
            }
            if (current == null) { //end of the line not find it
                return false;
            }
        }
            //find the node
            //第一种，无节点（也就是叶节点，直接干掉
            if(current.leftChild==null&&current.rightChild==null){
                //如果是root节点
                if(current==root){
                    root=null;
                }else if(isLeftChild){
                    parent.leftChild=null;
                }else{
                    parent.rightChild=null;
                }
            }
            //第二种，有一个子节点，并且是左子节点     也有可能是父亲的左节点或者是父亲的右节点
            else if(current.rightChild==null){
                if(current==root){
                    root=current.leftChild;
                }else if(isLeftChild){ //左子
                    parent.leftChild=current.leftChild; //①父亲的左子树
                }else{
                    parent.rightChild=current.leftChild;//②父亲的右子树
                }
            }
            //第二种，有一个子节点，并且右子节点
            else if(current.leftChild==null){
                if(current==root){
                    root=current.rightChild;
                }else if(isLeftChild){
                    parent.leftChild=current.rightChild;
                }else{
                    parent.rightChild=current.rightChild;
                }
            }
            //第三种， 两个子树，需要找到后继节点
            else{
                Node successor=getSuccessor(current);
                if(current==root){
                    root=successor;
                }else if(isLeftChild){
                    parent.leftChild=successor;
                }else {
                    parent.rightChild=successor;
                }
                successor.leftChild=current.leftChild;
            }// end else 第三种情况
        return true;
        }

    /**
     * 获取中序后续结点
      * @param delNode
     * @return
     */
    private Node getSuccessor(Node delNode) {
        Node succesorParent=delNode;
        Node successor=delNode;
        Node current=delNode.rightChild;  //右子树
        while (current!=null){
            succesorParent=successor;
            successor=current;
            current=current.leftChild; //左子树
        }
        if(successor!=delNode.rightChild){//如果后继节点不是右子树
            succesorParent.leftChild=successor.rightChild;
            successor.rightChild=delNode.rightChild;
        }
        return successor;
    }

    public void traverse(int traverseType){
        switch (traverseType){
            case 1:
                System.out.print("\n 前序遍历  根左右");
                preOrder(root);
                break;
            case 2:
                System.out.print("\n 中序遍历  左根右");
                inOrder(root);
                break;
            case 3:
                System.out.print("\n 后序遍历  左右根");
                postOrder(root);
        }
    }

    private void postOrder(Node root) {
        if (root!=null){
            inOrder(root.leftChild);
            inOrder(root.rightChild);
            System.out.print(root.iData+" ");
        }
    }

    private void inOrder(Node localRoot) {
       if (localRoot!=null){
            inOrder(localRoot.leftChild);
            System.out.print(localRoot.iData+" ");
            inOrder(localRoot.rightChild);
        }
    }

    private void preOrder(Node localRoot) {
        if(localRoot!=null){
            System.out.print(localRoot.iData+" ");
            preOrder(localRoot.leftChild);
            preOrder(localRoot.rightChild);
        }
    }

    public void displayTree(){
        Stack globalStack=new Stack();
        globalStack.push(root);
        int nBlanks=32;
        boolean isRowEmpty=false;
        System.out.println("..........................................");
        while (isRowEmpty==false){
            Stack localStack=new Stack();
            isRowEmpty=true;
            for (int j = 0; j <nBlanks ; j++) {
                System.out.print(' ');
            }
            while (globalStack.isEmpty()==false){
                Node temp=(Node) globalStack.pop();
                if(temp!=null){
                    System.out.print(temp.iData);
                    localStack.push(temp.leftChild);
                    localStack.push(temp.rightChild);
                    if(temp.leftChild!=null||temp.rightChild!=null){
                        isRowEmpty=false;
                    }
                }else {
                    System.out.print("--");
                    localStack.push(null);
                    localStack.push(null);
                }
                for (int j = 0; j < nBlanks * 2 - 2; j++) {
                    System.out.print(' ');
                }
            }//end while
            System.out.println();
            nBlanks/=2;
            while (localStack.isEmpty()==false){
                globalStack.push(localStack.pop());
            }
        }// end while isRowEmpty is false
        System.out.println("....................................");
    }

}















